Automatic test generation for sequential circuits is a difficult task. Several different techniques are used to accomplish this task. Complete scan testing, for example, transforms the sequential circuit into a computational circuit by making all the memory elements controllable and observable. However, it may not be possible to design every circuit for complete scan testing and the cost in terms of performance and testing overhead may be prohibitive. Partial scan testing is a more cost-effective alternative in which only a subset of the memory elements are tested thereby reducing delay and area overhead as well as test application time.
Known partial scan methods include those based upon testability measures, test pattern generation or structural analysis. Other methods rely upon heuristics and a cost function to select test memory elements. Some other partial scan methods start with a set of functional vectors to detect as many faults as possible, then combinational test pattern generation is used to find additional memory elements that provide extra controllability and observability to detect the remaining faults. In other methods, memory elements are selected so that the remaining circuit is acyclic.
High level synthesis methods have been used to generate easily testable data paths. The presence of loops in a sequential circuit has been shown to be primarily responsible for making automatic test pattern generation difficult. Accordingly, methods have been devised to synthesize data paths without loops by using proper scheduling and assignment, and scan registers to break loops. In addition to the presence of control data flow graph (CDFG) loops, other types of loops can be introduced in the data path during hardware sharing. In an article by S. Dey, M. Potkonjak, and R. Roy entitled "Exploring Hardware-Sharing in High Level Synthesis for Partial Scan Optimization," paper B.1, ICCAD93, November 1993, there is described a synthesis for testability method that first selects scan variables which can be assigned to scan registers in order to break all the CDFG loops present. Subsequently, scheduling and assignment is performed while attempting to avoid the formation of other types of loops encountered by reusing the selected scan registers.